package leetcode.D500.T451;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

class Solution {
    public String frequencySort(String s) {
        StringBuilder sb = new StringBuilder();
        Map<Character, Integer> map = new HashMap<>();

        for(int i=0; i<s.length(); ++i) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        LinkedList<Character>[] buckets = new LinkedList[s.length()];
        for(Character key: map.keySet()) {
            int count = map.get(key);
            if(buckets[count-1] == null) {
                buckets[count-1] = new LinkedList<>();
            }
            buckets[count-1].add(key);
        }
        for(int i=buckets.length-1; i>=0; --i) {
            if(buckets[i] == null) {
                continue;
            }
            while(!buckets[i].isEmpty()) {
                char c = buckets[i].removeFirst();
                int count = map.get(c);
                for(int j=0; j<count; ++j) {
                    sb.append(c);
                }
            }
        }
        return sb.toString();
    }
}